package 剑指offer;

public class 剑指Offer36二叉搜索树与双向链表 {
    public TreeNode treeToDoublyList(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode node = treeHelper(root);
        TreeNode flag = node;
        while (flag != null && flag.right != null){
            flag = flag.right;
        }
        node.left = flag;
        flag.right = node;

        return node;
    }
    public TreeNode treeHelper(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode leftHead = treeHelper(root.left);
        TreeNode leftTail = leftHead;
        while (leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        if (leftTail != null){
            leftTail.right = root;
            root.left = leftTail;
        }
        TreeNode rightHead = treeHelper(root.right);
        if (rightHead != null){
            rightHead.left = root;
            root.right = rightHead;
        }

        return leftHead == null ? root : leftHead;
    }
}
